영어 공부

  1. start_day 인덱스부터 스트릭을 계산해 나가기 시작한다.
  2. 주어진 p로 구할 수 있는 가장 큰 날짜 optimal_day 를 구한다. with 이분탐색 :: last-true
  3. start_day..=optimal_day 구간의 영어공부를 한 날과 추가로 체크할 수 있는 날 p의 합이 곧 start_day에서의 최적의 스트릭이다.

풀이

삽질을 좀 했다. 파라메트릭 서치를 이용하는 것 까지는 파악했으나, 결정문제 안에서 O(N), O(N*N)의 시간을 사용하면 아무 의미가 없어져 버리는 것이었다!

sol1

최대 20만개의 정수를 벡터에 넣기가 싫어서 메인함수에서 입력을 전역적으로 처리한 뒤에 solution을 호출하는 방향으로 계획했으나… 별로 좋은 생각이 아니었다.

  1. 이 문제는 길이 L짜리 스트릭을 생성할 수 있는지 에 관한 문제임이 틀림없다! ⇒ f(L)=True,False

  2. 길이 L짜리 Sliding Window를 사용하면 영어공부를 완료한 날들 사이 비어있는 칸의 수를 셀 수 있고, 한 번 훑었을 때 비어있는 칸의 수가 p 이하이기만 하면 True를, 아니면 False를 통과시키기로 했다.

    1. Sliding Window를 구현하기 위해 필요한 건 영어공부를 완료한 날들을 훑기 위한 배열이었다. 하지만 최대 1,000,000개의 날짜를 단순 int형 배열에 담기엔 너무 많았고, bitset 을 직접 구현하는 것으로 최적화를 달성할 수 있었다.

    • custom bitset

      총 10^6개의 비트, unsigned int 자료형이 32비트니까 총 31250개의 int형이 있으면 된다.

      constexpr u32 MAX_DAY = 1'000'000;
constexpr u32 MAX_N = 200'000;
constexpr u32 MAX_P = 200'000;

namespace bitset {

constexpr u32 BITS = sizeof(u32) * 8;
constexpr u32 MAX_BUCKETS = MAX_DAY / BITS;

static array<u32, MAX_BUCKETS + 1> _bitset;

inline void init() { _bitset.fill(0); }
inline bool check(u32 idx) {
  auto bucket = idx / BITS;
  auto bit = idx % BITS;
  return (_bitset[bucket] >> bit) & 1;
}
/**set bit to true*/
inline void set(u32 idx) {
  auto bucket = idx / BITS;
  auto bit = idx % BITS;
  _bitset[bucket] |= (1 << bit);
}
/**set bit to false*/
inline void reset(u32 idx) {
  auto bucket = idx / BITS;
  auto bit = idx % BITS;
  _bitset[bucket] &= ~(1 << bit); // X & 0b111111011111
}

} // namespace bitset

  3. 이 문제는 True → False 순서로 이루어져 있고, 가장 마지막 True를 찾으면 되는 문제이다.

    1. 가장 마지막 True는 가장 처음 False 를 찾은 뒤에 해당 인덱스 -1 하면 된다.
    2. 이분탐색 알고리즘의 정수가 바로 아래의 코드에 들어있다. 전략패턴을 사용하여 세부사항을 분리했다.

    • first_true, first_false

      /**
@breif:
  False -- True 구간의 첫번째 True를 찾아줘요.
@param:
 - begin: inclusive
 - end: exclusive
 - pred: predicate, 이를 사용하여 first_true도, first_false도 가능.
*/
template <typename T, class Predicate>
inline T first_true(T begin, T end, Predicate const &pred) {
  auto l = begin;
  auto r = end;
  while (l != r) {
    auto m = l + (r - l) / 2; // overflow 방지
    if (pred(m)) {
      // 구간 [m, r) 을 볼 필요 없으니 다음 구간은 [l, m)이다.
      r = m;
    } else {
      // 구간 [l, m + 1)를 볼 필요 없으니 다음 구간은 [m+1, r)이다.
      l = m + 1;
    }
  }
  return l;
}

      /**
@breif:
  True -- False 구간의 첫번째 False를 찾아줘요.
*/
template <typename T, class Predicate>
inline T first_false(T begin, T end, Predicate const &pred) {
  auto pred_inversed = [&pred](auto i) { return !pred(i); };
  return first_true(begin, end, pred_inversed);
}

sol2

좀 더 효율적으로 수행하기 위해 영어공부한 날짜들 사이의 간격을 사용해보면 어떨까? 해서 solution 함수의 시그니처를 변경했다.

sol3

멘탈이 나가버렸다. 블로그 글을 검색해보기도 했는데 머리에 들어오는 것은 없었다. 일단 가장 근본적인 문제를 다시 생각해 보기로 했다.

start 번째 날짜부터 셀 수 있는 가장 긴 streak을 찾아라 ⇒ 이분탐색 with last-true

days 3 5 6 10 11
blanks 0 1 0 3 0
blanks_cum 0 1 1 4 4

start = 0일때 탐색 범위는 [0,5)이다.

  1. 주어진 p로 메꿀 수 있는 가장 큰 날짜(last-true)를 구한다
  2. 남은 p를 그 뒤에 붙여 스트릭 개수를 구한다.

수도코드로는 다음과 같다. streak 는 start ~ optimal_day 까지 수강한 영어수업의 개수와 그 사이에 비어있는 공백을 모두 메운 값이 된다.

for start in range(len(days)):
	optimal_day = last_true(start, N)
	streak = p
	streak += optimal_day - (start - 1)
	answer = max(answer, streak)

last_true() 는 다음과 같이 구현할 수 있겠다.

def last_true(start, N):
	l = start
	r = N
	while l < r:
		mid = l + (r - l) / 2
		blank = blanks_cum[mid] - blanks_cum[start]
		if (p < blank):
			# cannot fill, move left range into [l, mid)
			r = mid
		else:
			# can fill, move right range into [mid + 1, r)
			l = mid + 1
	return l - 1 # l 은 현재 first-false를 가리키고 있다. last-true는 바로 전 원소임

참고로 아래 `binary_search` 함수는 아예 날짜가 아니라 최대스트릭을 리턴하니 읽을때 주의하기 바란다.

```cpp
/**
@breif:
  bitset을 사용하지 않는 이진검색
@param:
 - days: 정렬된 상태를 보장하는 영어공부를 실시한 날짜들
 - p: 추가적으로 영어공부를 했다고 뻥칠 수 있는 날들의 개수
*/
inline int solution(vector<u32> const &days, u32 p) {

  // 0번째 날짜부터 i번째 날짜까지 공백의 개수
  vector<u32> blanks;
  std::adjacent_difference(days.begin(), days.end(), //
                           std::back_inserter(blanks),
                           [](auto a, auto b) { return a - b - 1; });
  blanks[0] = 0; // 0번째 날짜는 세지 않는다.
  std::partial_sum(blanks.begin(), blanks.end(), blanks.begin());

  int max = 0;
  // i번째 날짜부터 셀 수 있는 가장 긴 streak
  for (size_t i = 0; i < days.size(); ++i) {

    max = std::max(max, binary_search(blanks, i, p));
  }

  return max;
}
```

sol4

sol3은 이분탐색을 별도로 구현했지만, 밥을 먹고 돌아와보니 이걸 처음에 만들었던 first-true, first-false 에 익명함수로도 사용할 수 있을 것 같았다. 그래서 더 간결하게 만든 소스코드이다.